package xyz.robinbingo.leetcode.a20.b06.c14;

import java.util.Arrays;

public class Solution {
    public int findBestValue(int[] arr, int target) {
        int length = arr.length;
        int avg = (int) Math.round(target * 1.0 / length);
        Arrays.sort(arr);
        int max = arr[length - 1];
        int min = arr[0];
        if (max <= avg) {
            return max;
        }
        if (min >= avg) {
            return avg;
        }
        int m = Integer.MAX_VALUE;
        int result = Integer.MAX_VALUE;
        for (int i = avg; i <= max; i++) {
            int sum = 0;
            for (int value : arr) {
                sum += Math.min(value, i);
            }
            int abs = Math.abs(sum - target);
            if (abs < m) {
                m = abs;
                result = i;
            }
        }
        return result;
    }
}